package q621_leastInterval;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    /*
    首先考虑如何最高效的向任务间隙中 插入 任务
    最先取出的必然是出现次数最多的任务 因为其执行之间的 间隙 是最多的
    假设出现次数最多的任务 其出现次数为 maxV 那么其间隙应该是 （maxV - 1） * （n） 当然为了考虑其本身执行的时间
    那么总的执行时间应该是 （maxV - 1） * （n + 1） + 1 (最后还有一个该任务 所以还要加一)
    假设一共有maxCount个任务 其出现次数都是最多的 那么时间就变为（maxV - 1） * （n + 1） + maxCount
    那么剩下的任务出现次数都比最大次数少
    我们从倒数第二行开始，按照反向列优先的顺序（即先放入靠左侧的列，同一列中先放入下方的行），
    依次放入每一种任务，并且同一种任务需要连续地填入。

    而上面的假设是建立于maxCount <= n + 1的情况下
    如果不满足的话 应该如何填入间隙中？
    实际上我们只需要绘图就可以了解到 如果超过了n + 1，那么我们同样的按照这样的方式排列 两种相同的任务之间的执行时间就必然超过了n
    所以此时最长时间就是task的数量
    因此最后只需要取max即可
     */
    public int leastInterval(char[] tasks, int n) {
        if (n == 0) return tasks.length;

        Map<Character, Integer> map = new HashMap<>();
        int maxV = 0, maxCount = 0;
        for (char task : tasks) {
            map.put(task, map.getOrDefault(task, 0) + 1);
            maxV = Math.max(maxV, map.get(task));
        }
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (entry.getValue() == maxV) ++maxCount;
        }

        return Math.max((maxV - 1) * (n + 1) + maxCount, tasks.length);

    }
}
